package 力扣日常刷题.木22一月.第04天0111;

/**
 * @author 帅小伙
 * @date 2022/1/11
 * @description 输入：n = 2
 * 输出：2
 * 解释：
 * 第 1 个优美的排列是 [1,2]：
 * - perm[1] = 1 能被 i = 1 整除
 * - perm[2] = 2 能被 i = 2 整除
 * 第 2 个优美的排列是 [2,1]:
 * - perm[1] = 2 能被 i = 1 整除
 * - i = 2 能被 perm[2] = 1 整除
 * <p>
 * 链接：https://leetcode-cn.com/problems/beautiful-arrangement
 */
public class Demo07回溯中等优美的排列 {


    int ans = 0;
    int[] arr;
    boolean[] isUsed;

    public int countArrangement(int n) {
        arr = new int[n + 1];
        isUsed = new boolean[n + 1];
        dfs(1);
        return ans;
    }

    void dfs(int index) {
        if (index == arr.length) {
            ans++;
        }
        for (int i = 1; i < arr.length; i++) {
            if (!isUsed[i] && (i % index == 0 || index % i == 0)) {
                isUsed[i] = true;
                dfs(index+1);
                isUsed[i] = false;
            }
        }

    }


}
